1. Field of the Invention
The present invention relates to an encoding technique of an image.
2. Description of the Related Art
Conventionally, as a method of encoding an image, methods such as JPEG encoding using orthogonal transformation and the like are available. JPEG encoding will be briefly described below. An image is divided into blocks of 8×8 pixels, and each block undergoes DCT (discrete cosine transformation). 8×8 DCT coefficient values obtained by the DCT are quantized using a quantization table. Since the quantization table normally has larger quantization step widths for higher frequency components, quantized values are smaller and the frequency of occurrence of “0” becomes higher for higher frequency components.
Subsequently, the quantized values are encoded. In this case, different encoding processes are applied to DC and AC components. DC components undergo predictive coding since they have strong correlation between neighboring blocks, and then undergo Huffman encoding. Predictive coding is a method of encoding differences from DC component values of an immediately preceding block. Huffman encoding is an encoding method which assigns a short code to a value with a high frequency of occurrence and a long code to a value with a low frequency of occurrence, thus consequently shortening the overall code length. AC components undergo runlength encoding, and then Huffman encoding. Runlength encoding is an encoding method which encodes a value and its runlength, and the encoding efficiency improves as an identical value runs with a larger length. Note that the encoding efficiency is improved by zigzag-scanning the quantized values to form a run of zero values of high frequency components.
JPEG encoding is a good compression method for natural images. However, for images including characters, line arts, and the like, JPEG encoding readily generates mosquito noise due to loss of high frequency components of images. Also, JPEG encoding readily causes block distortion (block-shaped noise) due to loss of high frequency components and quantization errors of DC components.
By contrast, Japanese Patent Laid-Open No. 09-172636 discloses the following technique. That is, with this technique, an edge emphasizing device, which is adapted to emphasize edge components of inputted image data, does this edge emphasis in accordance with the contents of a quantization table used in quantization means, thereby reducing noise.
Also, Japanese Patent Laid-Open No. 06-164941 discloses the following technique. That is, with this technique, an image is divided into blocks that undergo orthogonal transformation and quantization processing using a criterion for sorting image regions into an important region and the remaining region, and quantization coefficients of blocks which do not belong to the important region are substituted by zero, thus partially maintaining high image quality.
As described above, the conventional encoding processing is executed by defining the upper left corner position in a certain block as a start point and making a raster or zigzag scan from that start point position. On the other hand, in order to improve the encoding efficiency, it is important to increase the probability of a run of identical values during a scan. However, in either the raster or zigzag scan, the scan end position is the lower right corner position of the block. That is, if data different from those which appear so far is located at that lower right corner position, encoded data of all data must be consequently generated, and the conventional encoding leaves much room to improve in terms of the encoding efficiency.
As methods of encoding images, predictive coding, orthogonal transformation encoding, and the like are available. In predictive coding, upon encoding a pixel of interest, its predicted value is calculated from surrounding pixels which have already been encoded, and the difference (predictive error) between that predicted value and an actual value of the pixel of interest is encoded. Normally, a shorter codeword is assigned with decreasing predictive error. Therefore, the amount of encoded data to be generated largely varies depending on the predicted value calculation method.
Hence, a technique for encoding an image by selectively using a plurality of predictive coding methods is known (for example, Japanese Patent Laid-Open No. 9-37246).
Also, a technique for converting a plurality of two-dimensional array data to be encoded into one-dimensional array data (scan method) is known (for example, Japanese Patent Laid-Open No. 2003-037843).
However, in the conventional image encoding techniques, since image data is encoded in a predetermined scan order, the encoding efficiency deteriorates depending on images.